/**
 * Project: Useful Programs
 * Package: tools
 */
package org.leumasjaffe.collections;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import org.eclipse.jdt.annotation.NonNullByDefault;

/**
 * Class Sort in file Sort.java
 * 
 * @author leumasjaffe
 * Created on: Jul 26, 2012
 * 
 * @deprecated Use {@link java.util.Arrays#sort(Object[])} and {@link java.util.Collections#sort(List)}
 * 
 */
@NonNullByDefault
@Deprecated
public abstract class Sort {
	
	/* In-place Insertion Sort */
	
	/**
	 * @param list
	 * @return
	 */
	public static <T extends Comparable<T>> List<T> insertionSort(List<T> list) {
		return insertionSort(list, 0, list.size());
	}
	
	/**
	 * @param list
	 * @param start
	 * @param end
	 * @return
	 */
	public static <T extends Comparable<T>> List<T> insertionSort(List<T> list,
			int start, int end) {
		T x;
		for (int i = start; i < end; i++) {
			x = list.get(i);
			for (int j = i-1; j >= -1; j--) {
				if (j == -1 || x.compareTo(list.get(j)) <= 0) {
					list.set(j+1, x);
					break;
				}
				else
					list.set(j+1, list.get(j));
			}
		}
		return list;
	}
	
	/**
	 * @param list
	 * @return
	 */
	public static <T extends Comparable<T>> ArrayList<T> insertionSort(ArrayList<T> list) {
		return (ArrayList<T>) insertionSort((List<T>) list);
	}
	
	/**
	 * @param list
	 * @return
	 */
	public static <T extends Comparable<T>> LinkedList<T> insertionSort(LinkedList<T> list) {
		return (LinkedList<T>) insertionSort((List<T>) list);
	}
	
	/**
	 * @param list
	 * @return
	 */
	public static <T extends Comparable<T>> T[] insertionSort(T[] list) {
		return insertionSort(list, 0, list.length);
	}
	
	/**
	 * @param list
	 * @param start
	 * @param end
	 * @return
	 */
	public static <T extends Comparable<T>> T[] insertionSort(T[] list, int start, int end) {
		for (int i = start; i < end; i++) {
			for (int j = i-1; j >= -1; j--) {
				if (j == -1 || list[i].compareTo(list[j]) <= 0) {
					list[j+1] = list[i];
					break;
				}
				else
					list[j+1] =  list[j];
			}
		}
		return list;
	}
	
	/* Quick Sort */
	
	/**
	 * @param array
	 * @return
	 */
	public static <T extends Comparable<T>> List<T> quickSort(List<T> array) {
		return quickSort(array, 0, array.size());
	}
	
	/**
	 * @param array
	 * @param start
	 * @param end
	 * @return
	 */
	public static <T extends Comparable<T>> List<T> quickSort(List<T> array,
			int start, int end) {
		int index = partition(array, start, end);
		if (start < index-1)
			quickSort(array, start, index-1);
		if (index < end)
			quickSort(array, index, end);
		return array;
	}
	
	/**
	 * @param array
	 * @return
	 */
	public static <T extends Comparable<T>> ArrayList<T> quickSort(ArrayList<T> array) {
		return (ArrayList<T>) quickSort((List<T>) array);
	}
	
	/**
	 * @param array
	 * @return
	 */
	public static <T extends Comparable<T>> LinkedList<T> quickSort(LinkedList<T> array) {
		return (LinkedList<T>) quickSort((List<T>) array);
	}
	
	/**
	 * @param array
	 * @return
	 */
	public static <T extends Comparable<T>> T[] quickSort(T[] array) {
		return quickSort(array, 0, array.length);
	}
	
	/**
	 * @param array
	 * @param start
	 * @param end
	 * @return
	 */
	public static <T extends Comparable<T>> T[] quickSort(T[] array, int start, int end) {
		int index = partition(array, start, end);
		if (start < index-1)
			quickSort(array, start, index-1);
		if (index < end)
			quickSort(array, index, end);
		return array;
	}
	
	/**
	 * @param array
	 * @param start
	 * @param end
	 * @return
	 */
	private static <T extends Comparable<T>> int partition(T[] array, int start, int end) {
		int i = start, j = end;
		T pivot = array[(end-start)/2];
		
		while (i <= j) {
			while (array[i].compareTo(pivot) < 0)
				i++;
			while (pivot.compareTo(array[j]) > 0)
				j--;
			if (i <= j)
				Swap.swap(array, i++, j--);
		}	
		return i;
	}
	
	/**
	 * @param array
	 * @param start
	 * @param end
	 * @return
	 */
	private static <T extends Comparable<T>> int partition(List<T> array, int start, int end) {
		int i = start, j = end;
		T pivot = array.get((end-start)/2);
		
		while (i <= j) {
			while (array.get(i).compareTo(pivot) < 0)
				i++;
			while (pivot.compareTo(array.get(j)) > 0)
				j--;
			if (i <= j) 
				Swap.swap(array, i++, j--);
		}	
		return i;
	}
	
	/* Merge Sort */
	
	/**
	 * @param list
	 * @return
	 */
	public static <T extends Comparable<T>> ArrayList<T> mergeSort(ArrayList<T> list) {
		return (ArrayList<T>) mergeSort((List<T>) list);
	}
	
	/**
	 * @param list
	 * @return
	 */
	public static <T extends Comparable<T>> LinkedList<T> mergeSort(LinkedList<T> list) {
		return (LinkedList<T>) mergeSort((List<T>) list);
	}
	
	/**
	 * @param list
	 * @param start
	 * @param end
	 * @return
	 */
	public static <T extends Comparable<T>> ArrayList<T> mergeSort(ArrayList<T> list, 
			int start, int end) {
		return (ArrayList<T>) mergeSort((List<T>) list, start, end);
	}
	
	/**
	 * @param list
	 * @param start
	 * @param end
	 * @return
	 */
	public static <T extends Comparable<T>> LinkedList<T> mergeSort(LinkedList<T> list, 
			int start, int end) {
		return (LinkedList<T>) mergeSort((List<T>) list, start, end);
	}
	
	/**
	 * @param list
	 * @return
	 */
	public static <T extends Comparable<T>> List<T> mergeSort(List<T> list) {
		return mergeSort(list, 0, list.size());
	}
	
	/**
	 * @param list
	 * @param start
	 * @param end
	 * @return
	 */
	public static <T extends Comparable<T>> List<T> mergeSort(List<T> list,
			int start, int end) {
		if (start - end <= 1)
			return list;
		else
			return split(list, start, end);
	}
	
	/**
	 * @param array
	 * @return
	 */
	public static <T extends Comparable<T>> T[] mergeSort(T[] array) {
		return mergeSort(array, 0, array.length);
	}
	
	/**
	 * @param array
	 * @param start
	 * @param end
	 * @return
	 */
	public static <T extends Comparable<T>> T[] mergeSort(T[] array, int start, int end) {
		if (start - end <= 1)
			return array;
		else
			return split(array, start, end);
	}
	
	/**
	 * @param array
	 * @param start
	 * @param end
	 * @return
	 */
	@SuppressWarnings("unchecked")
	private static <T extends Comparable<T>> T[] split(T[] array, int start, int end) {
		int i, mid = (end-start) >>> 1;
		T[] arr1 = (T[]) new Object[mid - start];
		T[] arr2 = (T[]) new Object[end - mid];
				
		for (i = start; i < mid; i++)
			arr1[i] = array[i];
		for (i=mid; i < end; i++)
			arr2[i-mid] = array[i];
		
		T[] array1 = mergeSort(arr1, start, mid);
		T[] array2 = mergeSort(arr2, mid, end);
		
		T[] mergeArr = merge(array1, array2, array, start, end);
		
		arr1 = null;
		arr2 = null;
		array1 = null;
		array2 = null;
		
		return mergeArr;
	}
	
	/**
	 * @param array1
	 * @param array2
	 * @param array
	 * @param start
	 * @param end
	 * @return
	 */
	private static <T extends Comparable<T>> T[] merge(T[] array1, T[] array2,
			T[] array, int start, int end) {
		int size1 = array1.length, size2 = array2.length;
		int i = 0, j = 0;
		
		for(int n = start; n < end; n++) {
			if (j >= size2 || (i < size1 && array1[i].compareTo(array2[i]) <= 0))
				array[n] = array1[i++];
			else 
				array[n] = array2[j++];
		}
		
		return array;
	}
	
	/**
	 * @param array
	 * @param start
	 * @param end
	 * @return
	 */
	@SuppressWarnings("unchecked")
	private static <T extends Comparable<T>> List<T> split(List<T> array,
			int start, int end) {
		int i, mid = (end-start) >>> 1;
		T[] arr1 = (T[]) new Object[mid - start];
		T[] arr2 = (T[]) new Object[end - mid];
				
		for (i = start; i < mid; i++)
			arr1[i] = array.get(i);
		for (i=mid; i < end; i++)
			arr2[i-mid] = array.get(i);
		
		T[] array1 = mergeSort(arr1, start, mid);
		T[] array2 = mergeSort(arr2, mid, end);
		
		List<T> mergeArr = merge(array1, array2, array, start, end);
		
		arr1 = null;
		arr2 = null;
		array1 = null;
		array2 = null;
		
		return mergeArr;
	}
	
	/**
	 * @param array1
	 * @param array2
	 * @param array
	 * @param start
	 * @param end
	 * @return
	 */
	private static <T extends Comparable<T>> List<T> merge(T[] array1, T[] array2,
			List<T> array, int start, int end) {
		int size1 = array1.length, size2 = array2.length;
		int i = 0, j = 0;
		
		for(int n = start; n < end; n++) {
			if (j >= size2 || (i < size1 && array1[i].compareTo(array2[i]) <= 0))
				array.set(n, array1[i++]);
			else 
				array.set(n, array2[j++]);
		}
		
		return array;
	}
	
}
